class Solution
{
public:
    void dfs(vector<int> &A, vector<int> &B, vector<int> &C, int n)
    {
        if (n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        else
        {
            dfs(A, C, B, n - 1);
            C.push_back(A.back());
            A.pop_back();
            dfs(B, A, C, n - 1);
        }
    }
    void hanota(vector<int> &A, vector<int> &B, vector<int> &C)
    {
        dfs(A, B, C, A.size());
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        if (list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }

        //     ListNode* arr = new ListNode;
        //     ListNode* list3 = arr;
        //     while(list1 && list2)
        //     {
        //         if(list1->val <= list2->val)
        //         {
        //             list3->next = list1;
        //             list1 = list1->next;
        //         }
        //         else if(list1->val > list2->val)
        //         {
        //             list3->next = list2;
        //             list2 = list2->next;
        //         }
        //         list3 = list3->next;
        //     }
        //     if(list1)
        //     {
        //         list3 -> next = list1;
        //     }
        //     if(list2)
        //     {
        //         list3 -> next = list2;
        //     }
        //     return arr->next;
        // }
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        // ListNode* p = head;
        // ListNode* q = nullptr;
        // while(p)
        // {
        //     ListNode* next = p->next;
        //     p->next = q;
        //     q = p;
        //     p=next;
        // }
        // return q;

        if (head == nullptr || head->next == nullptr) // 只有一个节点和一个节点都没有
        {
            return head;
        }
        ListNode *newnode = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newnode;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        auto phead = new ListNode;
        phead->next = head;
        auto prev = head;
        auto fail = phead;
        while (prev && prev->next)
        {
            auto next = prev->next;
            prev->next = next->next;
            next->next = prev;
            fail->next = next;

            fail = prev;
            prev = prev->next;
        }
        return phead->next;

        if(head==nullptr || head->next==nullptr)
            return head;
        ListNode* newnode = swapPairs(head->next->next);
        // 要先存一下我们最终返回结果，也就是转换之后第二个元素变成了第一个元素
        // 否则我们下面转换之后，第二个元素成为第一个元素了，没有人指向
        // 1->2->3 ---- 2->1->3 ---- 2->head->newnode  没有人指向2
        auto result = head->next;
        head->next->next = head;
        head->next = newnode;
        return result;
    }
};
class Solution
{
public:
    double Pow(double x, long long n)
    {
        if (n == 0)
            return 1;
        double result = Pow(x, n / 2);
        result *= result;
        return n % 2 == 0 ? result : result * x; // 可能n是奇数，但是没关系，多乘一次x就行了
    }
    double myPow(double x, int n)
    {
        // return pow(x,n);
        return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, (long long)n);
        // double result = 0.0;
        // if(n<0)
        //     result = Pow(x,-(long long)n);
        // else
        //     result = Pow(x,(long long)n);
        // return n<0?1.0/result:result;
    }
};